# coding=utf-8
# Fibonacci.py

Fib = {}

def Fibonacci(n):
    global Fib
    if Fib.has_key(n): return Fib[n]
    if n == 0: return 1
    if n == 1: return 1
    Fib[n] = Fibonacci(n-1) + Fibonacci(n-2)
    return Fib[n]

if __name__ == '__main__':
    for i in range(5000):
        print Fibonacci(i)
